import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        boolean[][] row = new boolean[9][9];
        boolean[][] col= new boolean[9][9];
        boolean[][] box = new boolean[9][9];
        for(int i=0; i < 9; i++) {
            for(int j=0; j < 9; j++) {
                if(board[i][j] != '.') {
                    int num = board[i][j]-'1';
                    int boxIndex = i/3 * 3 + j/3;
                    if(row[i][num] || col[j][num] || box[boxIndex][num]) {
                        return false;
                    }else {
                        row[i][num] = true;
                        col[j][num] = true;
                        box[boxIndex][num] = true;
                    }
                }
            }
        }
        return true;
    }

    public boolean containsDuplicate(int[] nums) {
        Set<Integer> hashSet = new HashSet<>();
        for(int x : nums) {
            if(!hashSet.contains(x)) {
                hashSet.add(x);
            }else {
                return true;
            }
        }
        return false;
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer,Integer> hashMap = new HashMap<>();
        for(int i=0; i < nums.length; i++) {
            if(!hashMap.containsKey(nums[i])) {
                hashMap.put(nums[i],i);
            }else {
                if(Math.abs(i - hashMap.get(nums[i])) <= k) {
                    return true;
                }else {
                    hashMap.put(nums[i],i);
                }
            }
        }
        return false;
    }

    public char findTheDifference(String s, String t) {
        Map<Character,Integer> hashMap1 = new HashMap<>();
        for(int i=0; i < s.length(); i++) {
            char ch =s.charAt(i);
            if (!hashMap1.containsKey(ch)) {
                hashMap1.put(ch,1);
            }else {
                hashMap1.put(ch,hashMap1.get(ch)+1);
            }
        }

        Map<Character,Integer> hashMap2 = new HashMap<>();
        for(int i=0; i < t.length(); i++) {
            char ch =t.charAt(i);
            if (!hashMap2.containsKey(ch)) {
                hashMap2.put(ch,1);
            }else {
                hashMap2.put(ch,hashMap2.get(ch)+1);
            }
        }
        for (Map.Entry<Character,Integer> entry: hashMap2.entrySet()) {
            if (hashMap1.containsKey(entry.getKey())) {
                int val1 = entry.getValue();
                int val2 = hashMap1.get(entry.getKey());
                if (val1 != val2) {
                    return entry.getKey();
                }
            }else {
                return entry.getKey();
            }
        }
        return '0';
    }

    public int findMaxLength(int[] nums) {
        Map<Integer,Integer> hashMap = new HashMap<>();
        int sum = 0;
        int maxLength = 0;
        hashMap.put(sum,-1);
        for(int i=0; i < nums.length; i++) {
            if(nums[i] == 1) {
                sum++;
            }else {
                sum--;
            }
            if(hashMap.containsKey(sum)) {
                int prevIndex = hashMap.get(sum);
                maxLength = Math.max(maxLength,i - prevIndex);
            }else {
                hashMap.put(sum,i);
            }
        }
        return maxLength;
    }

}
